package arithmetic1.recall;

/*
    迷宫回溯问题:
        从起点开始，找到一条路径可以通往终点
    数组里面0代表路，1代表墙，2表示走过的路径,3代表走过但是走不通
    假设起点坐标为(1,1) 终点坐标为(6,5)
 */
public class MiGong {
    public static void main(String[] args) {
        //定义8行7列的二维数组
        int arr[][]=new int[8][7];
        //初始化地图
        init(arr);

        //打印地图
        for (int[] arr1:arr){
            for (int num:arr1){
                System.out.print(num+"  ");
            }
            System.out.println();
        }
        System.out.println("---------------------");

        //寻找路径
        findRoad(arr,1,1);

        //打印地图
        for (int[] arr1:arr){
            for (int num:arr1){
                System.out.print(num+"  ");
            }
            System.out.println();
        }

    }

    //初始化二维数组
    public static void init(int arr[][]){
        //将4周都变成墙
        for (int i=0;i<7;i++){
            arr[0][i]=1;
            arr[7][i]=1;
        }
        for(int i=0;i<8;i++){
            arr[i][0]=1;
            arr[i][6]=1;
        }
        //再设置两个墙
        arr[3][1]=1;
        arr[3][2]=1;

//        arr[1][2]=1;
//        arr[2][2]=1;

    }

    //假定寻找路径的顺序为：下  右  上  左
    public static boolean findRoad(int arr[][],int startI,int startJ){
       if(arr[6][5]==2){    //已经找到终点
           return true;
       }else {  //还没有找到终点
           if (arr[startI][startJ]==0){ //改点可以走
               //将改点标记为2
               arr[startI][startJ]=2;
               //按照顺序找其他的路
               if(findRoad(arr,startI+1,startJ)){
                   return true;
               }else if(findRoad(arr,startI,startJ+1)){
                   return true;
               }else if(findRoad(arr,startI-1,startJ)){
                   return true;
               }else if(findRoad(arr,startI,startJ-1)){
                   return true;
               }else {      //该点4个方向都走不通
                   //回溯，将走过的路标记为3
                   arr[startI][startJ]=3;
                   return false;
               }
           }else {  //该点为1(墙)  2(已经走过)  3(走过了走不通)
               return false;
           }
       }
    }

}
